import java.util.*;

public class Solution {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向：上、下、左、右

    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word); // 将所有单词插入到 Trie 中
        }

        Set<String> ans = new HashSet<>(); // 使用 HashSet 去重
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                dfs(board, trie, i, j, ans); // 从每个单元格开始深度优先搜索
            }
        }

        return new ArrayList<>(ans); // 将结果转换为 List 返回
    }

    public void dfs(char[][] board, Trie now, int i1, int j1, Set<String> ans) {
        if (!now.children.containsKey(board[i1][j1])) { // 如果当前字符不在 Trie 的子节点中，直接返回
            return;
        }
        char ch = board[i1][j1];
        now = now.children.get(ch); // 移动到 Trie 的对应子节点
        if (!"".equals(now.word)) { // 如果当前 Trie 节点是一个单词的结尾
            ans.add(now.word); // 将单词加入结果集
            now.word = ""; // 防止重复添加
        }

        board[i1][j1] = '#'; // 标记当前单元格已访问
        for (int[] dir : dirs) { // 遍历四个方向
            int i2 = i1 + dir[0], j2 = j1 + dir[1];
            if (i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length) { // 确保不越界
                dfs(board, now, i2, j2, ans); // 递归搜索下一个单元格
            }
        }
        board[i1][j1] = ch; // 恢复当前单元格的值
    }
}

class Trie {
    String word; // 用于存储完整的单词
    Map<Character, Trie> children; // 子节点

    public Trie() {
        this.word = "";
        this.children = new HashMap<>();
    }

    public void insert(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            if (!cur.children.containsKey(c)) {
                cur.children.put(c, new Trie());
            }
            cur = cur.children.get(c);
        }
        cur.word = word; // 在 Trie 的叶子节点存储完整的单词
    }
    public static void main(String[] args) {
        char[][] board = {
                {'o', 'a', 'a', 'n'},
                {'e', 't', 'a', 'e'},
                {'i', 'h', 'k', 'r'},
                {'i', 'f', 'l', 'v'}
        };
        String[] words = {"oath", "pea", "eat", "rain"};

        Solution solution = new Solution();
        List<String> result = solution.findWords(board, words);
        System.out.println(result); // 输出结果
    }
}

